package pfq.demo.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序:
 * <p>
 * 对相邻的元素进行两两比较，顺序相反则进行交换，这样每一趟会将最小或最大的元素浮到顶端
 * <p>
 * 时间复杂度
 * 最好：O(n)
 * 最坏：O(n^2)
 * 平均：O(n^2)
 */
public class BubbleSort {

    public static void main(String[] args) {

        int[] data = Arrays.copyOf(Utils.data(), Utils.data().length);
        System.out.println("排序前：" + Arrays.toString(data));
        bubbleSort(data);
        System.out.println("排序后：" + Arrays.toString(data));

    }

    /**
     * 冒泡
     *
     * @param arr 待排序的数组
     */
    public static void bubbleSort(int[] arr) {

        // 设置一个标记，表示如果此次循环没有进行交换，也就是说该序列已经有序，就不需要继续下去
        boolean flag = true;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {

                // 每次将较小值的索引赋给minIndex
                if (arr[i] > arr[j]) {
                    Utils.swap(arr, i, j);
                    flag = false;
                }

            }

            if (flag) {
                return;
            }

        }

    }


}
